# leetcode 2304, 网格中的最小路径代价

class Solution:
    def minPathCost(self, grid: List[List[int]], moveCost: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[float('inf')] * n for i in range(m)]  # dp[i][j]表示从第一行移动到第i行第j列的最小路径代价
        dp[0] = grid[0]
        for i in range(1, m):
            for j in range(n):
                for k in range(n):
                    val = grid[i - 1][k]
                    cost = dp[i - 1][k] + moveCost[val][j] + grid[i][j]
                    dp[i][j] = min(dp[i][j], cost)
        print(dp)
        return(min(dp[-1]))
